%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\section{Polynome, Galois Field, AES}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection{Polynome \buchmann{3.18}}

Allgemeine Darstellung eines Polynoms über $R$
\begin{displaymath}
f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}
\end{displaymath}
mit 
\begin{itemize}
\item $R$: kommutativer Ring mit Einselelement $1\neq0$
\item $x$: Variable über  $R$
\item $a_{0},\ldots,a_{n} \in R$: Koeffizienten
\item $n = \deg f$: Grad
\item $a_{n}\neq0$: Leitkoeffizient
\end{itemize}

Ist $f(x) = 0$, so heißt $x$ Nullstelle. Sind $a_{n}\neq0$ und $a_{n-1},\ldots,a_{0} = 0$, so heißt $f$ Monom. Menge aller Polynome über $R$ in $x$ wird mit $R[x]$ bezeichnet. 

\paragraph{Summe}
\begin{displaymath}
(g+h)(x)=(a_{n}+b_{m})x^{n}+\dots+(a_{1}+b_{1})x+(a_{0}+b_{0})
\end{displaymath}
Aufwand: $O(\max\{\deg g, \deg h\}+1)$ Additionen

\paragraph{Produkt}
\begin{displaymath}
(gh)(x)=c_{n+m}x^{n+m}+\dots+c_{1}x+c_{0}
\end{displaymath}
mit $c_{k}=\sum_{i=0}^{k} a_{i}b_{k-i}$ und $0\le k\le n+m$\\
Aufwand: $O((\deg g +1)(\deg h +1))$ Additionen, 
$O((\deg g +1)(\deg h +1))$ Multiplikationen

wobei g und h jeweils wie folgt definiert sind
\begin{displaymath}
g(x)=a_{n}x^{n}+\dots+a_{1}x+a_{0}
\end{displaymath}
\begin{displaymath}
h(x)=b_{m}x^{m}+\dots+b_{1}x+b_{0}
\end{displaymath}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection{Polynome über Körpern \buchmann{3.19}}

Ist $K$ ein Körper, dann ist $K[x]$ ein nullteilerfreier Polynomring. Mit $f,g \in K[x], f,g \neq0$ folgt $\deg(fg) = \deg f + \deg g$.

Ist $f,g \in K[x], g \neq0$ dann lasst sich $f = pg + r$ eindeutig bestimmen mit
\begin{itemize}
\item $q,r \in K[x]$: Polynome
\item $q$: Quotient
\item $r=f\mod g$: Rest
\item $r=f\mod g$: Rest
\item $\deg r < \deg g$
\end{itemize}

\paragraph{Beispiel für Polynomdivision} 
\ \newline
\polylongdiv{x^5 + x^4 + x^3 + x^2  + 1}{x^2  +x}
\ \newline
$\Rightarrow q(x) = x^{3}+x, r=1$\\

Es gelten folgende Regeln:
\begin{enumerate}
\item Mit $f,g \in K[x], g \neq0$ werden $O((\deg g +1)(\deg q +1))$ Operationen für $r=f\mod g$ benötigt.
\item Ist $f \in K[x], f \neq0$ und $a$ Nullstelle von $f$ gilt $(x-a)|f$ oder $f(x)=(x-a)q(x)$ mit $q \in K[x]$.
\item Ist $f \in K[x], f \neq0$ so hat $f(x) n$ Nullstellen mit $n\le \deg f$.
\end{enumerate}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection{Konstruktion endlicher Körper \buchmann{3.20}}

Wir konstruieren einen endlichen Körper (engl. galois field) 
\begin{displaymath}
\gf(p^{n}) = \text{Restklasse in } (\Z/p\Z)[X]\mod f 
\end{displaymath}
mit
\begin{itemize}
\item $p$: Primzahl, $n \in \N$
\item $f$: irreduzibles Polynom, $\deg f = n$
\end{itemize}

\paragraph{Definition} \hfill \\
Das Polynom $f$ heißt \emph{irreduzibel} gdw. $f=gh$ mit $g,h \in (\Z/p\Z)[X]$ impliziert $\deg g = 0$ oder  $\deg h = 0$.

Für verschiedene $f$ ergeben sich isomorphe, d.h. strukturgleiche Körper.

\paragraph{Beispiel}
\begin{displaymath}
\gf(2^{2}) \text{ mit } f(X)=X^{2}+X+1 = 
\end{displaymath}
\begin{alignat*}{4}
\{&&&0+&&f(X)(\Z/p\Z)[X],\\
&&&1+&&f(X)(\Z/p\Z)[X],\\
&X+&&0+&&f(X)(\Z/p\Z)[X],\\
&X+&&1+&&f(X)(\Z/p\Z)[X]&\}
\end{alignat*}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection[AES \buchmann{7}]{Advanced Encryption Standard (AES) \buchmann{7}}

AES ist ein Spezialfall der Rijndael-Chiffre, die aus folgenden Schritten besteht
\begin{enumerate}
\item KeyExpansion
\begin{itemize}
\item RotWord: Permutation (linear)
\item SubBytes: S-Box (nicht-linear)
\item XOR-Verknüpfung (linear)
\end{itemize}
\item Cipher
\begin{itemize}
\item SubBytes: S-Box (nicht-linear)
\item ShiftRows: Linksshift in Matrizen (linear)
\item MixColumns: Spaltentausch in Matrizen (linear)
\item AddRoundKey: XOR mit Rundenschlüssel  (linear)
\end{itemize}
\end{enumerate} 
\vspace*{1mm}

Dabei lassen sich Polynome mit Elementen von $\gf(2^{8})$ mit einem Byte identifizieren:
\begin{displaymath}
\gf(2^{8}) \text{ über } m(X)= X^{8}+ X^{4}+ X^{3}+ X+1
\end{displaymath}
\begin{displaymath}
\gf(2)(\alpha) \text{ wobei für } \alpha \text{ gilt } \alpha^{8}+ \alpha^{4}+ \alpha^{3}+ \alpha+1=0
\end{displaymath}
\begin{displaymath}
\alpha \text{ entspricht Nullstelle von }m(X)
\end{displaymath}
\begin{displaymath}
\text{Das Byte } b_{7}\cdots b_{0} \text{ entspricht den Element } \sum_{i=0}^{7} b_{i}\alpha^{i}
\end{displaymath}

\paragraph{Beispiel} \hfill \\
Das Byte $b = (0,0,0,0,0,0,1,1)$ entspricht dem Körperelement $\alpha+1$
